package q61_rotateRight;

import CommonClass.Common;
import CommonClass.Common.ListNode;
public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        ListNode head = Common.generateList(new int[]{1, 2, 3, 4});
        Common.printList(s.rotateRight(head, 1));

    }

    /**
     * 首先是遍历一遍链表来了解链表的长度，然后对k和len进行比较，如果可以整除，就可以直接返回head
     * 否则就需要找到断开的点，这里需要注意的是在tail位置先链接head形成环，
     * 需要向后找 len - (k % len)个节点，才是断开的点，而不是k % len
     * 然后先保存断开位置后一个节点，再断开，返回保存的后一个节点即可
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) {
            return head;
        }
        int len = 1;
        ListNode tail = head;
        while (tail.next != null){
            tail = tail.next;
            len++;
        }

        if (len - k % len == 0) {
            return head;
        }

        tail.next = head;
        for (int i = 0; i < len - k % len; i++) {
            tail = tail.next;
        }
        ListNode newhead = tail.next;
        tail.next = null;
        return newhead;
    }
}
